from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        #  空链表或者只有一个节点的链表直接返回就行了
        # if head == None or head.next == None:
        #     return head
        # # 递归做法
        # pre, cur, nxt = None, head, head.next
        # while cur is not None:
        #     cur.next = pre
        #     pre = cur
        #     cur = nxt
        #     if nxt is not None:
        #         nxt = nxt.next
        # return pre
        # 递归写法
        if head == None or head.next == None:
            return head
        tail = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return tail
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    # your test code here